The Transmission Control Protocol/Internet Protocol (TCP/IP) suite is a widely-used transport protocol in digital packet networks. The TCP is described by Postel in RFC 793 of the U.S. Defense Advanced Research Projects Agency (DARPA), entitled “Transmission Control Protocol: DARPA Internet Program Protocol Specification” (1981), which is incorporated herein by reference. TCP is a connection-oriented, end-to-end, full-duplex protocol, which provides for reliable inter-process communication between pairs of processes in host computers. The information exchanged between TCP peers is packed into datagrams termed segments, each segment comprising a TCP header followed by payload data. The segments are transported over the network in IP packets.
FIG. 1 is a schematic block diagram depicting a structure of a Transmission Control Protocol (TCP) segment header 10, as is known in the art and specified in RFC 793. Header 10 begins with a source port 12 and a destination port 14, which are 16-bit identifiers respectively indicating the origin and intended destination of the TCP segment. As noted, the TCP is a connection-oriented protocol, signifying that messages are exchanged between two identified end-points which have an established connection.
A logical communication channel established between pairs of sockets is termed a connection. Connections are established after a three-way handshake process has completed successfully. An important element in the reliability of the TCP is the use of sequence numbers. Each octet (8 bits) of payload data transmitted is assigned a sequence number by the sending process. Payload data is indicated as a data field 40. The receiving process is required to acknowledge receipt of all octets received, by sending an acknowledgment (ACK) verifying the last sequence number successfully received. Sequence numbers provide a way for the sender to identify missing payload data requiring re-transmission, as well as a way for the receiver to order payload data which arrives out of sequence. Thus, a sequence number 16 contains a sequence number for a first octet of payload data in the TCP segment payload. If an ACK flag 24 is set, an acknowledgment number 18 contains the value of the next sequence number the sender of the acknowledgment segment is expecting to receive.
The TCP header contains six flags indicative of additional control information. A RST flag 28 indicates a request to reset the connection. A SYN flag 30 indicates that the segment is part of the three-way handshake process. A PSH flag 26 directs the receiving process to make transmitted data available immediately to the application level without waiting for a timeout or full buffer. A FIN flag 30 indicates that the sender has no more data to send.
A window field 34 contains a number of bytes beginning with the one indicated in the acknowledgment field which the sender of the segment is willing to accept. Field 34 thus advertises to a recipient of the segment an effective maximum number of bytes which the sender is prepared to receive.
An options field 37 provides a way to extend the original protocol while preserving compatibility with earlier implementations. The options field is used to synchronize various parameters during connection establishment, e.g., window scale and maximum segment size. In addition, the options field can convey information which is useful on an established connection, for example a Selective Acknowledgment (SACK) option and a timestamp (TS) option. The SACK option is described by Mathis, et al. in RFC 2018 of the Network Working Group, entitled “TCP Selective Acknowledgment Options” (1996), which is incorporated herein by reference. The SACK option supplements acknowledgment number 18 by providing a way to recover quickly from a single or consecutive set of missing segments by using an additional Acknowledgment number indicating segments received after the missing segments.
The TS option is described by Jacobson, et al. in RFC 1323 of the Network Working Group, entitled “TCP Extensions for High Performance” (1992), which is incorporated herein by reference. The TS option supplies a way to measure round-trip delivery times for segments, i.e., the time between the transmission of a segment and the receipt of an acknowledgment for the segment. This facility allows a TCP implementation to adapt acknowledgment timers to dynamic network behavior.
For the past twenty years, TCP/IP has been implemented as a software suite, typically as a part of computer operating systems. Within the TCP/IP software suite, the TCP receiver function is the largest logical task. A number of authors have suggested strategies for enhancing the performance of TCP receiver processing. However, software implementations of TCP receiver logic are limited by operating system performance constraints, as well as inefficiencies deriving from the serial nature of program execution in general-purpose microprocessors and associated overhead.
FIG. 2 is a flowchart showing processing of TCP/IP segments by a receiver, as is known in the art. A process substantially similar to that illustrated by the flowchart is described in section 27.9 of TCP/IP Illustrated, Volume 2, by Wright and Stevens, published by Addison-Wesley. The flowchart distinguishes in a first comparison 41 between two paths by which incoming segments are handled. Comparison 41 categorizes the incoming segment as an in-order segment, defined as having a start sequence value equal to the value of acknowledgment number 18 (FIG. 1). Otherwise the incoming segment is categorized as an out-of-order segment.
In a fast path 42, followed when condition 41 is true, data in an incoming segment is appended to already received data. Path 42 is only followed providing a queue buffer holding out-of-order segments is empty, the incoming segment is an in-order segment, and a connection has already been established. Path 42 comprises steps 47 wherein incoming statistics are updated and data comprised in the segment are appended to a receive buffer.
In a slow path 43, followed when condition 41 is false, a series of conditions 44, 45, and 46 are evaluated to see if data in the incoming segment is stored in a queue buffer, or if the data may be used to fill a “hole” in data which has already been stored in the queue buffer. Condition 44 checks to see if a connection already exists, and if not, establishes a connection and places the incoming segment data in the queue buffer. Condition 45 checks to see if the segment is an out-of-order segment, and if it is, places the incoming segment data in the queue buffer. Condition 46 checks to see if the segment fills a hole in data in the queue buffer. If it is, the data fills the hole; if it is not, the data is placed in the queue buffer.
As long as network speed was the main factor limiting receiver rates, software implementations of TCP receiver logic provided adequate performance levels. However, with the advent of network speeds in the Gbps and 10 Gbps range, this is no longer the case. Faster TCP receiver processing is required. In an attempt to release the resulting bottleneck, attention has turned to the development of a dedicated hardware implementation, or acceleration, of TCP/IP receiver logic. Optimizing a hardware implementation calls for a new approach to the original specification in RFC 793. Among the issues to be addressed are maximization of parallel processing, efficient information passing, and rapid classification and handling of segments.